\section{Analysis}
\label{sec:approx}

We analyze approximation ratios of the algorithm presented in Section~\ref{sec:algo}, the guarantee depending on parameters of the algorithm. We divide the analysis into two parts: the first part is for the densest subgraph problem and the second for the at-least-$k$ densest subgraph problem. Although the second part subsumes the first part (if we ignore the value of constant approximation ratio), we present the first part since it has a simpler idea and a better approximation ratio.

\subsection{Analysis for the densest subgraph problem}

\begin{theorem}\label{theorem:approx densest}
Let $t$ be the time Algorithm~\ref{algo:densest} finishes, $V_i$ be the output of the algorithm, $H^*$ be the optimal solution and $T$ be the time of one round of Algorithm~\ref{algo:maintain} and \ref{algo:densest} (i.e., $T=cD\log_{1+\epsilon} n$ for some constant $c$). If $\rho_t(H^*)\geq 24Tr/\epsilon$ then Algorithm~\ref{algo:densest} gives, w.h.p., a $(2+\epsilon)$-approximation, i.e.,
$$\rho_t(V_i)\geq \rho_t(H^*)/(2+\epsilon)\,.$$
\end{theorem}

%We just mention the very high level idea of the proof here. The complete proof of this theorem is placed in Appendix~\ref{sec:app main one}.

The rest of this subsection is devoted to proving the above theorem.
%
Let $t$, $V_i$ and $H^*$ be as in the theorem statement (note that $\hat{V}$ in Algorithm~\ref{algo:densest} is empty when $k=0$). Let $t'$ be the time that $V_i$ is last computed by Algorithm~\ref{algo:maintain}. Let $t''$ be the time Algorithm~\ref{algo:maintain} starts counting the number of edges in $V_i$.
%
%
We prove the theorem using the following lemmas. The main idea is to first lower bound $\rho_{t''}(V_i)$ using $\rho_{t'}(H^*)$ and then use it to obtain a lower bound for $\rho_{t'}(V_i)$ in terms of $\rho_t(H^*)$. Finally, the proof is completed by lower bounding $\rho_t(V_i)$ in terms of $\rho_{t'}(V_i)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Move from appendix1.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{lemma}\label{lem: t prime prime to OPT}
$\rho_{t''}(V_i)>\frac{1-\delta}{2(1+\delta)^2}\rho_{t'}(H^*).$
\end{lemma}
\begin{proof}
Let $H'$ be the densest subgraph of $G_{t'}$. Note that
\begin{align}\label{eq:densest one}
\rho_{t'}(H^*)\leq \rho_{t'}(H')\,.
\end{align}
%
%It suffices to show that
%\begin{align}\label{eq:at time t prime}
%\rho_{t''}(V_i)\geq \frac{1-\delta}{2(1+\delta)^2}\rho_{t'}(H')
%\end{align}
%since $\rho_{t'}(H')\geq \rho_{t'}(H^*)$.
%
Let $i^*$ be the smallest index such that $V(H')\subseteq V_{i^*}$ and  $V(H')\not\subseteq V_{i^*+1}$.  Note that $i^*$ exists since the algorithm repeats until we get $V_j=\emptyset$. Let $v$ be any vertex in $V(H')\setminus V_{i^*}$. Let $H_{t', i}$ be the subgraph of $G_{t'}$ induced by nodes in $V_i$. Note that
\begin{align}\label{eq:densest two}
\rho_{t'}(H')\leq 2 \deg_{H'}(v) \leq 2\deg_{H_{t', i}}(v)\,. %\frac{|E_{t'}(V_{i^*}|}{2|V_{i^*}|}
\end{align}
%where $deg_{G_{t'}}(v)$ is the degree of $v$ in graph $G_{t'}$ and $E_{t'}(V_{i^*})$ is the number of edges in the subgraph of $G_{t'}$ induced by nodes in $V_{i^*}$.
%
The first inequality is because we can otherwise remove $v$ from $H'$ and get a subgraph of $G_{t'}$ that has a higher density than $H'$. The second inequality is because $H'\subseteq H_{t', i}$.
Since $v$ is removed from $V_{i^*}$,
\begin{align}\label{eq:densest three}
\deg_{H_{t',i}}(v)< (1+\delta) \frac{m_{i^*}}{n_{i^*}},
\end{align}
where $\delta=\epsilon/24$ as in Algorithm~\ref{algo:maintain}.
%
By the definition of $V_i$,
\begin{align}\label{eq:densest four}
\frac{m_{i^*}}{n_{i^*}}\leq \frac{m_i}{n_i}\,.
\end{align}
%
Note that $t-t''\leq T$ by the definition of $T$. Note also that $n_{i}\geq (1-\delta) |V_{i}|$ and $m_{i}\leq (1+\delta) |E_{t''}(V_{i})|$ with high probability\danupon{Need proof from previous section.}. It follows that
\begin{align}\label{eq:densest five}
\frac{m_{i}}{n_{i}}\leq \frac{1+\delta}{1-\delta}\rho_{t''}(V_{i})\,.
\end{align}
%(This is because for any $\delta\leq 1/3$, $\frac{1+\delta}{1-\delta}\leq 2$ and thus $\frac{1+\delta}{1-\delta}\leq \frac{1+\delta+2\delta}{1-\delta+\delta}=1+3\delta$.)
%
%
%Thus,
Combining Eq.\eqref{eq:densest one}-\eqref{eq:densest five}, we get $\rho_{t'}(H^*)<2\frac{(1+\delta)^2}{1-\delta}\rho_{t''}(V_i)$ and thus the lemma.
\end{proof}


We now make the following observation:
% Their proofs can be found in Appendix~\ref{sec:app main two}.
%The proof of Lemma~\ref{cor:t to OPT} uses Lemma~\ref{lem: t prime prime to OPT} above.
% no reference anywhere to \ref{cor:t to OPT}

\begin{observation}
\label{obs:43}
$\rho_{t'}(H^*)\geq (1-\delta)\rho_t(H^*)\,.$
\end{observation}
\begin{proof}
Note that $t-t'\leq T$ and thus $E_t(H^*)-E_{t'}(H^*)\leq Tr$. Since $\rho_t(H^*)\geq Tr/\delta$,
%\begin{align*}
$\rho_{t'}(H^*)  \geq \frac{\rho_{t}(H^*)\cdot |V(H^*)|-T r}{|V(H^*)|}
 \geq \rho_{t}(H^*)-Tr
 > (1-\delta)\rho_{t}(H^*)\,.$
%\end{align*}
\end{proof}

We now combine the above Lemma~\ref{lem: t prime prime to OPT} and Observation~\ref{obs:43} to obtain the following lemma:

%\begin{corollary} \labe{simplecor}
%$\rho_{t''}(V_i)>\frac{(1-\delta)^2}{2(1+\delta)^2}\rho_{t}(H^*).$
%\end{corollary}
%\begin{proof}
%This follows by directly combining Lemma~\ref{lem: t prime prime to OPT} and Observation~\ref{obs:43}.
%\end{proof}

\begin{lemma}
\label{lem:45}
$\rho_{t'}(V_i) > (\frac{(1-\delta)^2}{2(1+\delta)^2}-\delta)\rho_{t}(H^*)\,.$
\end{lemma}
\begin{proof}
By directly combining Lemma~\ref{lem: t prime prime to OPT} and Observation~\ref{obs:43} we get the following:
$$\rho_{t''}(V_{i})> \frac{(1-\delta)^2}{2(1+\delta)^2}\rho_{t}(H^*)\geq \frac{(1-\delta)^2}{2(1+\delta)^2\delta} Tr\,.$$
Moreover, observe that there are at most $Tr$ edges removed from $V_i$ in total, i.e., $E_{t''}(V_i)-E_{t}(\
V_i)\leq Tr$. Thus
%
\begin{align*}
\rho_{t'}(V_i) &\geq \frac{\rho_{t''}(V_i)\cdot |V_i|-T r}{|V_i|}
 \geq \rho_{t''}(V_i)-Tr
 > \left(1-\frac{2(1+\delta)^2\delta}{(1-\delta)^2}\right)\rho_{t''}(V_i)\\
& > \left(1-\frac{2(1+\delta)^2\delta}{(1-\delta)^2}\right)\left(\frac{(1-\delta)^2}{2(1+\delta)^2}\rho_{t}(H^*)\right)
 = \left(\frac{(1-\delta)^2}{2(1+\delta)^2}-\delta\right)\rho_{t}(H^*)\,.
%& \geq \frac{\rho_{t'}(H^*)}{2(1+7\delta)} &\mbox{(since $\delta =\epsilon/28 \leq 1/28$)}\\
%& = \frac{\rho_{t'}(H^*)}{2(1+\epsilon/4)}
\end{align*}
%
%This proves Eq.~\eqref{eq:at time t prime} and the lemma.
\end{proof}

%\begin{observation}
%$\rho_t(V_i) \geq (\frac{(1-\delta)^2}{2(1+\delta)^2}-2\delta)\rho_t(H^*)\,.$
%\end{observation}

We are now ready to prove the theorem.

\begin{proof}[Proof of Theorem~\ref{theorem:approx densest}]
Note that $t-t'\leq T$ and thus $E_{t'}(V_i)-E_{t}(V_i)\leq Tr$. Note that
$\rho_{t'}(V_i)> \beta\rho_{t}(H^*)\geq \beta Tr/\delta,$
where $\beta=\frac{(1-\delta)^2}{2(1+\delta)^2}-\delta$. We have
\begin{align*}
\rho_{t}(V_i)  \geq \frac{\rho_{t'}(V_i)\cdot |V_i|-T r}{|V_i|}
 \geq \rho_{t'}(V_i)-Tr
 > (1-\frac{\delta}{\beta})\rho_{t'}(V_i).
\end{align*}

Now using Lemma~\ref{lem:45} and the value of $\beta$, we get the following:
%
\begin{align*}
\rho_{t}(V_i) > (1-\frac{\delta}{\beta})\beta\rho_{t}(H^*)
 = (\beta-\delta)\rho_{t}(H^*)
 = \left(\frac{(1-\delta)^2}{2(1+\delta)^2}-2\delta\right)\rho_t(H^*).
\end{align*}
The theorem follows by observing that  $\frac{(1-\delta)^2}{2(1+\delta)^2}-2\delta\geq \frac{1}{2+\epsilon}$ for any $\epsilon\leq 1$ and $\delta \geq \epsilon/24$.
\end{proof}





\subsection{Analysis for the at-least-$k$ densest subgraph problem}

\begin{theorem}\label{thm:atleastktheorem}
Let $t$ be the time Algorithm~\ref{algo:densest} finishes, $V_i \cup \hat{V}$ be the output of the algorithm, $H^*$ be the optimal solution and $T$ be the time of one iteration of Algorithm~\ref{algo:maintain} and Algorithm~\ref{algo:densest} (so $T=O(D\log_{1+\epsilon} n)$). If $k\rho_t(H^*)\geq 24Tr/\epsilon$ then Algorithm~\ref{algo:densest} returns a set $V_i\cup \hat{V}$ of size at least $k$ that is, w.h.p., a $(3+\epsilon)$-approximated solution, i.e.,
$$\rho_t(V_i\cup \hat{V})\geq \rho_t(H^*)/(3+\epsilon)\,.$$
\end{theorem}

The proof of this theorem is in the full version \cite{fullversion}, and we just mention the main idea here. The proof follows a similar framework as that of Theorem~\ref{theorem:approx densest}.

Let $t$, $V_i$ and $H^*$ be as in the theorem statement. Let $t'$ be the time that $V_i$ is last computed by Algorithm~\ref{algo:maintain}. Let $t''$ be the time Algorithm~\ref{algo:maintain} starts counting the number of edges in $V_i$. The crucial difference here is to obtain a strong lower bound for $\rho_{t''}(V_i\cup \hat{V})$ in terms of $\rho_{t'}(H^*)$ and $\rho_t(H^*)$. This is then translated to a lower bound on $\rho_{t'}(V_i\cup \hat{V})$ and subsequently $\rho_{t}(V_i\cup \hat{V})$ to complete the proof. The crucial lemma and its proof turn out to be more involved than that of the densest subgraph theorem and the case-based analysis is detailed in the full version \cite{fullversion}.

